package middle;

import java.util.HashMap;
import java.util.Map;

public class Solution_1143 {

    public int longestCommonSubsequence(String text1, String text2) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chars_1 = text1.toCharArray();
        char[] chars_2 = text2.toCharArray();
        // 状态转移方程 res[i, j] = max(res[i - 1, j], res[i, j - 1], (s1[i] == s2[j] && res[i - 1, j - 1] + 1))
        // arrays[i][j][0] chars_1(0 ~ i) 和 chars_2(0 ~ j) 字符串中 最长的子序列长度
        int[][] arrays = new int[chars_1.length][chars_2.length];
        for (int i = 0; i < chars_1.length; i++) {
            map.put(chars_1[i], i);
            for (int j = 0; j < chars_2.length; j++) {
                int count; // chars_1[0, i] 和 chars_2[0 , j]的最长子序列长度
                if (chars_1[i] == chars_2[j]) {
                    if (i == 0 || j == 0) {
                        count = 1;
                    } else {
                        count = arrays[i - 1][j - 1] + 1;
                    }
                } else {
                    int kk = map.getOrDefault(chars_2[j], -1); // 字母chars_2[j] 在chars_1中最后一次出现的位置
                    if (kk < 0) {
                        // 说明在 chars_1[0, i] 里面，没有和 chars_2[j] 相同的字符，那么 res[i, j]等价于res[i, j-1]
                        if (j == 0) {
                            count = 0;
                        } else {
                            count = arrays[i][j - 1];
                        }
                    } else {
                        if (j == 0) {
                            count = 1;
                        } else {
                            if (kk == 0) {
                                count = Math.max(1, arrays[i][j - 1]);
                            } else {
                                count = Math.max(arrays[kk - 1][j - 1] + 1, arrays[i][j - 1]);
                            }
                        }
                    }
                }
                arrays[i][j] = count;
            }
        }
        return arrays[chars_1.length - 1][chars_2.length - 1];
    }

    public static void main(String[] args) {
        Solution_1143 model = new Solution_1143();
        System.out.println(model.longestCommonSubsequence("abcde", "ace"));
        System.out.println(model.longestCommonSubsequence("abc", "abc"));
        System.out.println(model.longestCommonSubsequence("abc", "def"));
        System.out.println(model.longestCommonSubsequence("a", "b"));
        System.out.println(model.longestCommonSubsequence("a", "a"));
    }
}
